home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / B-C / Berkeley-yacc-mpw / lr0.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-14  |  11.3 KB  |  638 lines  |  [TEXT/MPS ]
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Robert Paul Corbett.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #ifndef lint
  38. static char sccsid[] = "@(#)lr0.c    5.3 (Berkeley) 1/20/91";
  39. #endif /* not lint */
  40.  
  41. #include "defs.h"
  42.  
  43. extern short *itemset;
  44. extern short *itemsetend;
  45. extern unsigned *ruleset;
  46.  
  47. int nstates;
  48. core *first_state;
  49. shifts *first_shift;
  50. reductions *first_reduction;
  51.  
  52. int get_state();
  53. core *new_state();
  54.  
  55. static core **state_set;
  56. static core *this_state;
  57. static core *last_state;
  58. static shifts *last_shift;
  59. static reductions *last_reduction;
  60.  
  61. static int nshifts;
  62. static short *shift_symbol;
  63.  
  64. static short *redset;
  65. static short *shiftset;
  66.  
  67. static short **kernel_base;
  68. static short **kernel_end;
  69. static short *kernel_items;
  70.  
  71.  
  72. allocate_itemsets()
  73. {
  74.     register short *itemp;
  75.     register short *item_end;
  76.     register int symbol;
  77.     register int i;
  78.     register int count;
  79.     register int max;
  80.     register short *symbol_count;
  81.  
  82.     count = 0;
  83.     symbol_count = NEW2(nsyms, short);
  84.  
  85.     item_end = ritem + nitems;
  86.     for (itemp = ritem; itemp < item_end; itemp++)
  87.     {
  88.     symbol = *itemp;
  89.     if (symbol >= 0)
  90.     {
  91.         count++;
  92.         symbol_count[symbol]++;
  93.     }
  94.     }
  95.  
  96.     kernel_base = NEW2(nsyms, short *);
  97.     kernel_items = NEW2(count, short);
  98.  
  99.     count = 0;
  100.     max = 0;
  101.     for (i = 0; i < nsyms; i++)
  102.     {
  103.     kernel_base[i] = kernel_items + count;
  104.     count += symbol_count[i];
  105.     if (max < symbol_count[i])
  106.         max = symbol_count[i];
  107.     }
  108.  
  109.     shift_symbol = symbol_count;
  110.     kernel_end = NEW2(nsyms, short *);
  111. }
  112.  
  113.  
  114. allocate_storage()
  115. {
  116.     allocate_itemsets();
  117.     shiftset = NEW2(nsyms, short);
  118.     redset = NEW2(nrules + 1, short);
  119.     state_set = NEW2(nitems, core *);
  120. }
  121.  
  122.  
  123. append_states()
  124. {
  125.     register int i;
  126.     register int j;
  127.     register int symbol;
  128.  
  129. #ifdef    TRACE
  130.     fprintf(stderr, "Entering append_states()\n");
  131. #endif
  132.     for (i = 1; i < nshifts; i++)
  133.     {
  134.     symbol = shift_symbol[i];
  135.     j = i;
  136.     while (j > 0 && shift_symbol[j - 1] > symbol)
  137.     {
  138.         shift_symbol[j] = shift_symbol[j - 1];
  139.         j--;
  140.     }
  141.     shift_symbol[j] = symbol;
  142.     }
  143.  
  144.     for (i = 0; i < nshifts; i++)
  145.     {
  146.     symbol = shift_symbol[i];
  147.     shiftset[i] = get_state(symbol);
  148.     }
  149. }
  150.  
  151.  
  152. free_storage()
  153. {
  154.     FREE(shift_symbol);
  155.     FREE(redset);
  156.     FREE(shiftset);
  157.     FREE(kernel_base);
  158.     FREE(kernel_end);
  159.     FREE(kernel_items);
  160.     FREE(state_set);
  161. }
  162.  
  163.  
  164.  
  165. generate_states()
  166. {
  167.     allocate_storage();
  168.     itemset = NEW2(nitems, short);
  169.     ruleset = NEW2(WORDSIZE(nrules), unsigned);
  170.     set_first_derives();
  171.     initialize_states();
  172.  
  173.     while (this_state)
  174.     {
  175.     closure(this_state->items, this_state->nitems);
  176.     save_reductions();
  177.     new_itemsets();
  178.     append_states();
  179.  
  180.     if (nshifts > 0)
  181.         save_shifts();
  182.  
  183.     this_state = this_state->next;
  184.     }
  185.  
  186.     finalize_closure();
  187.     free_storage();
  188. }
  189.  
  190.  
  191.  
  192. int
  193. get_state(symbol)
  194. int symbol;
  195. {
  196.     register int key;
  197.     register short *isp1;
  198.     register short *isp2;
  199.     register short *iend;
  200.     register core *sp;
  201.     register int found;
  202.     register int n;
  203.  
  204. #ifdef    TRACE
  205.     fprintf(stderr, "Entering get_state(%d)\n", symbol);
  206. #endif
  207.  
  208.     isp1 = kernel_base[symbol];
  209.     iend = kernel_end[symbol];
  210.     n = iend - isp1;
  211.  
  212.     key = *isp1;
  213.     assert(0 <= key && key < nitems);
  214.     sp = state_set[key];
  215.     if (sp)
  216.     {
  217.     found = 0;
  218.     while (!found)
  219.     {
  220.         if (sp->nitems == n)
  221.         {
  222.         found = 1;
  223.         isp1 = kernel_base[symbol];
  224.         isp2 = sp->items;
  225.  
  226.         while (found && isp1 < iend)
  227.         {
  228.             if (*isp1++ != *isp2++)
  229.             found = 0;
  230.         }
  231.         }
  232.  
  233.         if (!found)
  234.         {
  235.         if (sp->link)
  236.         {
  237.             sp = sp->link;
  238.         }
  239.         else
  240.         {
  241.             sp = sp->link = new_state(symbol);
  242.             found = 1;
  243.         }
  244.         }
  245.     }
  246.     }
  247.     else
  248.     {
  249.     state_set[key] = sp = new_state(symbol);
  250.     }
  251.  
  252.     return (sp->number);
  253. }
  254.  
  255.  
  256.  
  257. initialize_states()
  258. {
  259.     register int i;
  260.     register short *start_derives;
  261.     register core *p;
  262.  
  263.     start_derives = derives[start_symbol];
  264.     for (i = 0; start_derives[i] >= 0; ++i)
  265.     continue;
  266.  
  267.     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
  268.     if (p == 0) no_space();
  269.  
  270.     p->next = 0;
  271.     p->link = 0;
  272.     p->number = 0;
  273.     p->accessing_symbol = 0;
  274.     p->nitems = i;
  275.  
  276.     for (i = 0;  start_derives[i] >= 0; ++i)
  277.     p->items[i] = rrhs[start_derives[i]];
  278.  
  279.     first_state = last_state = this_state = p;
  280.     nstates = 1;
  281. }
  282.  
  283.  
  284. new_itemsets()
  285. {
  286.     register int i;
  287.     register int shiftcount;
  288.     register short *isp;
  289.     register short *ksp;
  290.     register int symbol;
  291.  
  292.     for (i = 0; i < nsyms; i++)
  293.     kernel_end[i] = 0;
  294.  
  295.     shiftcount = 0;
  296.     isp = itemset;
  297.     while (isp < itemsetend)
  298.     {
  299.     i = *isp++;
  300.     symbol = ritem[i];
  301.     if (symbol > 0)
  302.     {
  303.         ksp = kernel_end[symbol];
  304.         if (!ksp)
  305.         {
  306.         shift_symbol[shiftcount++] = symbol;
  307.         ksp = kernel_base[symbol];
  308.         }
  309.  
  310.         *ksp++ = i + 1;
  311.         kernel_end[symbol] = ksp;
  312.     }
  313.     }
  314.  
  315.     nshifts = shiftcount;
  316. }
  317.  
  318.  
  319.  
  320. core *
  321. new_state(symbol)
  322. int symbol;
  323. {
  324.     register int n;
  325.     register core *p;
  326.     register short *isp1;
  327.     register short *isp2;
  328.     register short *iend;
  329.  
  330. #ifdef    TRACE
  331.     fprintf(stderr, "Entering new_state(%d)\n", symbol);
  332. #endif
  333.  
  334.     if (nstates >= MAXSHORT)
  335.     fatal("too many states");
  336.  
  337.     isp1 = kernel_base[symbol];
  338.     iend = kernel_end[symbol];
  339.     n = iend - isp1;
  340.  
  341.     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  342.     p->accessing_symbol = symbol;
  343.     p->number = nstates;
  344.     p->nitems = n;
  345.  
  346.     isp2 = p->items;
  347.     while (isp1 < iend)
  348.     *isp2++ = *isp1++;
  349.  
  350.     last_state->next = p;
  351.     last_state = p;
  352.  
  353.     nstates++;
  354.  
  355.     return (p);
  356. }
  357.  
  358.  
  359. /* show_cores is used for debugging */
  360.  
  361. show_cores()
  362. {
  363.     core *p;
  364.     int i, j, k, n;
  365.     int itemno;
  366.  
  367.     k = 0;
  368.     for (p = first_state; p; ++k, p = p->next)
  369.     {
  370.     if (k) printf("\n");
  371.     printf("state %d, number = %d, accessing symbol = %s\n",
  372.         k, p->number, symbol_name[p->accessing_symbol]);
  373.     n = p->nitems;
  374.     for (i = 0; i < n; ++i)
  375.     {
  376.         itemno = p->items[i];
  377.         printf("%4d  ", itemno);
  378.         j = itemno;
  379.         while (ritem[j] >= 0) ++j;
  380.         printf("%s :", symbol_name[rlhs[-ritem[j]]]);
  381.         j = rrhs[-ritem[j]];
  382.         while (j < itemno)
  383.         printf(" %s", symbol_name[ritem[j++]]);
  384.         printf(" .");
  385.         while (ritem[j] >= 0)
  386.         printf(" %s", symbol_name[ritem[j++]]);
  387.         printf("\n");
  388.         fflush(stdout);
  389.     }
  390.     }
  391. }
  392.  
  393.  
  394. /* show_ritems is used for debugging */
  395.  
  396. show_ritems()
  397. {
  398.     int i;
  399.  
  400.     for (i = 0; i < nitems; ++i)
  401.     printf("ritem[%d] = %d\n", i, ritem[i]);
  402. }
  403.  
  404.  
  405. /* show_rrhs is used for debugging */
  406. show_rrhs()
  407. {
  408.     int i;
  409.  
  410.     for (i = 0; i < nrules; ++i)
  411.     printf("rrhs[%d] = %d\n", i, rrhs[i]);
  412. }
  413.  
  414.  
  415. /* show_shifts is used for debugging */
  416.  
  417. show_shifts()
  418. {
  419.     shifts *p;
  420.     int i, j, k;
  421.  
  422.     k = 0;
  423.     for (p = first_shift; p; ++k, p = p->next)
  424.     {
  425.     if (k) printf("\n");
  426.     printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  427.         p->nshifts);
  428.     j = p->nshifts;
  429.     for (i = 0; i < j; ++i)
  430.         printf("\t%d\n", p->shift[i]);
  431.     }
  432. }
  433.  
  434.  
  435. save_shifts()
  436. {
  437.     register shifts *p;
  438.     register short *sp1;
  439.     register short *sp2;
  440.     register short *send;
  441.  
  442.     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  443.             (nshifts - 1) * sizeof(short)));
  444.  
  445.     p->number = this_state->number;
  446.     p->nshifts = nshifts;
  447.  
  448.     sp1 = shiftset;
  449.     sp2 = p->shift;
  450.     send = shiftset + nshifts;
  451.  
  452.     while (sp1 < send)
  453.     *sp2++ = *sp1++;
  454.  
  455.     if (last_shift)
  456.     {
  457.     last_shift->next = p;
  458.     last_shift = p;
  459.     }
  460.     else
  461.     {
  462.     first_shift = p;
  463.     last_shift = p;
  464.     }
  465. }
  466.  
  467.  
  468.  
  469. save_reductions()
  470. {
  471.     register short *isp;
  472.     register short *rp1;
  473.     register short *rp2;
  474.     register int item;
  475.     register int count;
  476.     register reductions *p;
  477.     register short *rend;
  478.  
  479.     count = 0;
  480.     for (isp = itemset; isp < itemsetend; isp++)
  481.     {
  482.     item = ritem[*isp];
  483.     if (item < 0)
  484.     {
  485.         redset[count++] = -item;
  486.     }
  487.     }
  488.  
  489.     if (count)
  490.     {
  491.     p = (reductions *) allocate((unsigned) (sizeof(reductions) +
  492.                     (count - 1) * sizeof(short)));
  493.  
  494.     p->number = this_state->number;
  495.     p->nreds = count;
  496.  
  497.     rp1 = redset;
  498.     rp2 = p->rules;
  499.     rend = rp1 + count;
  500.  
  501.     while (rp1 < rend)
  502.         *rp2++ = *rp1++;
  503.  
  504.     if (last_reduction)
  505.     {
  506.         last_reduction->next = p;
  507.         last_reduction = p;
  508.     }
  509.     else
  510.     {
  511.         first_reduction = p;
  512.         last_reduction = p;
  513.     }
  514.     }
  515. }
  516.  
  517.  
  518. set_derives()
  519. {
  520.     register int i, k;
  521.     register int lhs;
  522.     register short *rules;
  523.  
  524.     derives = NEW2(nsyms, short *);
  525.     rules = NEW2(nvars + nrules, short);
  526.  
  527.     k = 0;
  528.     for (lhs = start_symbol; lhs < nsyms; lhs++)
  529.     {
  530.     derives[lhs] = rules + k;
  531.     for (i = 0; i < nrules; i++)
  532.     {
  533.         if (rlhs[i] == lhs)
  534.         {
  535.         rules[k] = i;
  536.         k++;
  537.         }
  538.     }
  539.     rules[k] = -1;
  540.     k++;
  541.     }
  542.  
  543. #ifdef    DEBUG
  544.     print_derives();
  545. #endif
  546. }
  547.  
  548. free_derives()
  549. {
  550.     FREE(derives[start_symbol]);
  551.     FREE(derives);
  552. }
  553.  
  554. #ifdef    DEBUG
  555. print_derives()
  556. {
  557.     register int i;
  558.     register short *sp;
  559.  
  560.     printf("\nDERIVES\n\n");
  561.  
  562.     for (i = start_symbol; i < nsyms; i++)
  563.     {
  564.     printf("%s derives ", symbol_name[i]);
  565.     for (sp = derives[i]; *sp >= 0; sp++)
  566.     {
  567.         printf("  %d", *sp);
  568.     }
  569.     putchar('\n');
  570.     }
  571.  
  572.     putchar('\n');
  573. }
  574. #endif
  575.  
  576.  
  577. set_nullable()
  578. {
  579.     register int i, j;
  580.     register int empty;
  581.     int done;
  582.  
  583.     nullable = MALLOC(nsyms);
  584.     if (nullable == 0) no_space();
  585.  
  586.     for (i = 0; i < nsyms; ++i)
  587.     nullable[i] = 0;
  588.  
  589.     done = 0;
  590.     while (!done)
  591.     {
  592.     done = 1;
  593.     for (i = 1; i < nitems; i++)
  594.     {
  595.         empty = 1;
  596.         while ((j = ritem[i]) >= 0)
  597.         {
  598.         if (!nullable[j])
  599.             empty = 0;
  600.         ++i;
  601.         }
  602.         if (empty)
  603.         {
  604.         j = rlhs[-j];
  605.         if (!nullable[j])
  606.         {
  607.             nullable[j] = 1;
  608.             done = 0;
  609.         }
  610.         }
  611.     }
  612.     }
  613.  
  614. #ifdef DEBUG
  615.     for (i = 0; i < nsyms; i++)
  616.     {
  617.     if (nullable[i])
  618.         printf("%s is nullable\n", symbol_name[i]);
  619.     else
  620.         printf("%s is not nullable\n", symbol_name[i]);
  621.     }
  622. #endif
  623. }
  624.  
  625.  
  626. free_nullable()
  627. {
  628.     FREE(nullable);
  629. }
  630.  
  631.  
  632. lr0()
  633. {
  634.     set_derives();
  635.     set_nullable();
  636.     generate_states();
  637. }
  638.